// 对于字符串 "arcaea"，其子序列包括 "aca", "ara", "aaa" 等，这些子序列的首尾字符都是相同的。

function solution(s) {
  const MOD = 998244353;
  const n = s.length;
  let dp = Array.from({ length: n }, () => Array(n).fill(0));

  // Initialize the dp array for single character subsequences
  for (let i = 0; i < n; i++) {
    dp[i][i] = 1;
  }

  // Fill the dp array
  for (let length = 2; length <= n; length++) {
    for (let i = 0; i <= n - length; i++) {
      let j = i + length - 1;
      if (s[i] === s[j]) {
        dp[i][j] = (1 + dp[i + 1][j] + dp[i][j - 1]) % MOD;
      } else {
        dp[i][j] = (dp[i + 1][j] + dp[i][j - 1] - dp[i + 1][j - 1] + MOD) % MOD;
      }
    }
  }

  // Sum up all valid subsequences
  let result = 0;
  for (let i = 0; i < n; i++) {
    for (let j = i + 1; j < n; j++) {
      result = (result + dp[i][j]) % MOD;
    }
  }

  return result;
}

function main() {
  console.log(solution("arcaea") === 28);
  console.log(solution("abcabc") === 18);
  console.log(solution("aaaaa") === 31);
}

main();